package lcr.t38;

import java.util.Stack;

// https://www.bilibili.com/video/BV1my4y1Z7jj?
// 单调栈
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        if (temperatures == null || temperatures.length == 0) {
            return null;
        }

        int res[] = new int[temperatures.length];
        Stack<Integer> st = new Stack<>(); // 单调递增栈，用于记录扫描过的数据
        st.push(0);
        for (int i = 1; i < temperatures.length; i++) {
            while (!st.isEmpty() && temperatures[i] > temperatures[st.peek()]){
                // 当前坐标小于栈顶，记录结果
                int index = st.pop();
                res[index] = i - index;
            }
            st.push(i);
        }

        return res;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] res = s.dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73});
        for (int r : res) {
            System.out.println(r);
        }
    }
}